<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Optimized Bubble Sort Visualization</title>
    <script src="https://cdn.tailwindcss.com"></script>
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css">
    <style>
        .bar {
            transition: all 0.3s ease;
            border-radius: 5px 5px 0 0;
            display: flex;
            align-items: flex-end;
            justify-content: center;
            color: white;
            font-weight: bold;
            position: relative;
        }
        .bar-value {
            position: absolute;
            bottom: -25px;
            font-size: 14px;
        }
        .comparing {
            background-color: #f59e0b !important;
        }
        .swapping {
            background-color: #ef4444 !important;
        }
        .sorted {
            background-color: #10b981 !important;
        }
        .active {
            background-color: #3b82f6 !important;
        }
        .optimized {
            background-color: #8b5cf6 !important;
        }
    </style>
</head>
<body class="bg-gray-100 min-h-screen flex flex-col items-center py-8">
    <div class="container mx-auto px-4">
        <h1 class="text-3xl font-bold text-center text-gray-800 mb-6">Optimized Bubble Sort Visualization</h1>

        <div class="bg-white rounded-lg shadow-lg p-6 mb-8">
            <div class="flex justify-between items-center mb-6">
                <div class="flex space-x-4">
                    <button id="startBtn" class="bg-blue-500 hover:bg-blue-600 text-white px-4 py-2 rounded-md flex items-center">
                        <i class="fas fa-play mr-2"></i> Start
                    </button>
                    <button id="pauseBtn" class="bg-yellow-500 hover:bg-yellow-600 text-white px-4 py-2 rounded-md flex items-center" disabled>
                        <i class="fas fa-pause mr-2"></i> Pause
                    </button>
                    <button id="resetBtn" class="bg-red-500 hover:bg-red-600 text-white px-4 py-2 rounded-md flex items-center">
                        <i class="fas fa-redo mr-2"></i> Reset
                    </button>
                </div>

                <div class="flex items-center">
                    <span class="mr-2 text-gray-700">Speed:</span>
                    <input id="speedControl" type="range" min="50" max="1000" value="300" class="w-32">
                    <span id="speedValue" class="ml-2 text-gray-700">300ms</span>
                </div>
            </div>

            <div class="flex justify-center mb-4">
                <div id="arrayContainer" class="flex items-end h-64 space-x-2"></div>
            </div>

            <div class="flex justify-center space-x-6 text-sm text-gray-600">
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-blue-500 mr-2"></div>
                    <span>Active</span>
                </div>
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-yellow-500 mr-2"></div>
                    <span>Comparing</span>
                </div>
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-red-500 mr-2"></div>
                    <span>Swapping</span>
                </div>
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-green-500 mr-2"></div>
                    <span>Sorted</span>
                </div>
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-purple-500 mr-2"></div>
                    <span>Optimized</span>
                </div>
            </div>

            <div id="statusText" class="text-center mt-4 text-gray-700 font-medium"></div>
        </div>

        <div class="bg-white rounded-lg shadow-lg p-6">
            <h2 class="text-xl font-semibold text-gray-800 mb-4">Algorithm Explanation</h2>
            <div class="prose max-w-none">
                <p class="text-gray-700 mb-4">
                    The optimized bubble sort improves the basic algorithm by stopping early if no swaps are made during a pass, indicating the list is already sorted. This reduces the number of unnecessary comparisons when the array is nearly sorted.
                </p>
                <p class="text-gray-700 mb-4">
                    In this visualization, the purple color indicates when the optimization kicks in (no swaps were made in a complete pass). The algorithm will terminate early at this point.
                </p>
                <p class="text-gray-700">
                    The blue bars represent the current elements being compared. If they're out of order (turning red), they'll swap places. Yellow bars show the comparison phase, and green bars indicate elements that are in their final sorted position.
                </p>
            </div>
        </div>
    </div>

    <script>
        document.addEventListener('DOMContentLoaded', () => {
            // Initial array
            let originalArray = [4, 7, 1, 3, 5, 2, 6];
            let array = [...originalArray];
            let animationQueue = [];
            let isAnimating = false;
            let isPaused = false;
            let animationSpeed = 300;
            let animationTimeout = null;

            // DOM elements
            const arrayContainer = document.getElementById('arrayContainer');
            const startBtn = document.getElementById('startBtn');
            const pauseBtn = document.getElementById('pauseBtn');
            const resetBtn = document.getElementById('resetBtn');
            const speedControl = document.getElementById('speedControl');
            const speedValue = document.getElementById('speedValue');
            const statusText = document.getElementById('statusText');

            // Initialize the visualization
            function initializeArray() {
                arrayContainer.innerHTML = '';
                statusText.textContent = '';
                const maxValue = Math.max(...array);

                array.forEach((value, index) => {
                    const barHeight = (value / maxValue) * 100;
                    const bar = document.createElement('div');
                    bar.className = 'bar bg-blue-500';
                    bar.style.height = `${barHeight}%`;
                    bar.style.width = `${100 / array.length}%`;

                    const barValue = document.createElement('div');
                    barValue.className = 'bar-value text-gray-800';
                    barValue.textContent = value;

                    bar.appendChild(barValue);
                    bar.dataset.index = index;
                    bar.dataset.value = value;
                    arrayContainer.appendChild(bar);
                });
            }

            // Generate optimized bubble sort animations
            function generateAnimations() {
                const animations = [];
                const arr = [...array];
                let optimized = false;

                for (let i = 0; i < arr.length - 1; i++) {
                    let swapped = false;

                    // Mark the beginning of a new pass
                    animations.push({ type: 'status', text: `Pass ${i+1}: Checking elements` });

                    for (let j = 0; j < arr.length - i - 1; j++) {
                        // Compare j and j+1
                        animations.push({ type: 'compare', indices: [j, j+1] });

                        if (arr[j] > arr[j+1]) {
                            // Swap j and j+1
                            animations.push({ type: 'swap', indices: [j, j+1] });
                            [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
                            swapped = true;
                        }

                        // Reset colors after comparison
                        animations.push({ type: 'reset', indices: [j, j+1] });
                    }

                    // Mark the last element as sorted
                    animations.push({ type: 'sorted', index: arr.length - i - 1 });

                    // Check if we need to optimize
                    if (!swapped) {
                        animations.push({ type: 'status', text: `Pass ${i+1}: No swaps detected - array is sorted!` });
                        animations.push({ type: 'optimized' });
                        optimized = true;
                        break;
                    }
                }

                // If not already optimized, mark remaining elements as sorted
                if (!optimized) {
                    for (let i = 0; i < arr.length; i++) {
                        animations.push({ type: 'sorted', index: i });
                    }
                }

                return animations;
            }

            // Process animations
            function processAnimations() {
                if (animationQueue.length === 0) {
                    isAnimating = false;
                    startBtn.disabled = false;
                    pauseBtn.disabled = true;
                    statusText.textContent = 'Sorting completed!';
                    return;
                }

                if (isPaused) {
                    return;
                }

                const animation = animationQueue.shift();
                const bars = document.querySelectorAll('.bar');

                switch (animation.type) {
                    case 'compare':
                        bars[animation.indices[0]].classList.add('comparing');
                        bars[animation.indices[1]].classList.add('comparing');
                        break;

                    case 'swap':
                        bars[animation.indices[0]].classList.add('swapping');
                        bars[animation.indices[1]].classList.add('swapping');

                        // Swap the bars visually
                        setTimeout(() => {
                            const tempHeight = bars[animation.indices[0]].style.height;
                            const tempValue = bars[animation.indices[0]].dataset.value;

                            bars[animation.indices[0]].style.height = bars[animation.indices[1]].style.height;
                            bars[animation.indices[0]].dataset.value = bars[animation.indices[1]].dataset.value;
                            bars[animation.indices[0]].querySelector('.bar-value').textContent = bars[animation.indices[1]].dataset.value;

                            bars[animation.indices[1]].style.height = tempHeight;
                            bars[animation.indices[1]].dataset.value = tempValue;
                            bars[animation.indices[1]].querySelector('.bar-value').textContent = tempValue;
                        }, 10);
                        break;

                    case 'reset':
                        bars[animation.indices[0]].classList.remove('comparing', 'swapping');
                        bars[animation.indices[1]].classList.remove('comparing', 'swapping');
                        break;

                    case 'sorted':
                        bars[animation.index].classList.add('sorted');
                        bars[animation.index].classList.remove('active', 'comparing', 'swapping');
                        break;

                    case 'optimized':
                        // Mark all remaining unsorted bars as optimized
                        for (let i = 0; i < bars.length; i++) {
                            if (!bars[i].classList.contains('sorted')) {
                                bars[i].classList.add('optimized');
                            }
                        }
                        break;

                    case 'status':
                        statusText.textContent = animation.text;
                        break;
                }

                animationTimeout = setTimeout(processAnimations, animationSpeed);
            }

            // Start the animation
            function startAnimation() {
                if (isAnimating) return;

                isAnimating = true;
                isPaused = false;
                startBtn.disabled = true;
                pauseBtn.disabled = false;
                resetBtn.disabled = true;

                animationQueue = generateAnimations();
                processAnimations();
            }

            // Pause/resume animation
            function togglePause() {
                if (!isAnimating) return;

                isPaused = !isPaused;

                if (isPaused) {
                    pauseBtn.innerHTML = '<i class="fas fa-play mr-2"></i> Resume';
                    clearTimeout(animationTimeout);
                } else {
                    pauseBtn.innerHTML = '<i class="fas fa-pause mr-2"></i> Pause';
                    processAnimations();
                }
            }

            // Reset the visualization
            function reset() {
                clearTimeout(animationTimeout);
                isAnimating = false;
                isPaused = false;
                array = [...originalArray];
                animationQueue = [];

                startBtn.disabled = false;
                pauseBtn.disabled = true;
                resetBtn.disabled = false;
                pauseBtn.innerHTML = '<i class="fas fa-pause mr-2"></i> Pause';

                initializeArray();
            }

            // Event listeners
            startBtn.addEventListener('click', startAnimation);
            pauseBtn.addEventListener('click', togglePause);
            resetBtn.addEventListener('click', reset);

            speedControl.addEventListener('input', () => {
                animationSpeed = 1050 - speedControl.value; // Invert the value for more intuitive control
                speedValue.textContent = `${animationSpeed}ms`;
            });

            // Initialize
            initializeArray();
        });
    </script>
</body>
</html>